<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    1021. Distribute Coins in Binary Tree
   </h1>
   <p>
    Given the
    <code>
     root
    </code>
    of a binary tree with
    <code>
     N
    </code>
    nodes, each
    <code>
     node
    </code>
    &nbsp;in the tree has
    <code>
     node.val
    </code>
    coins, and there are
    <code>
     N
    </code>
    coins total.
   </p>
   <p>
    In one move, we may choose two adjacent nodes and move one coin from one node to another.&nbsp; (The move may be from parent to child, or from child to parent.)
   </p>
   <p>
    Return the number of moves required to make every node have exactly one coin.
   </p>
   <p>
    &nbsp;
   </p>
   <div>
    <p>
     <strong>
      Example 1:
     </strong>
    </p>
    <p>
     <strong>
      <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree1.png" style="width: 150px; height: 142px;">
     </strong>
    </p>
    <pre>
<strong>Input: </strong><span id="example-input-1-1">[3,0,0]</span>
<strong>Output: </strong><span id="example-output-1">2</span>
<strong>Explanation: </strong>From the root of the tree, we move one coin to its left child, and one coin to its right child.
</pre>
    <div>
     <p>
      <strong>
       Example 2:
      </strong>
     </p>
     <p>
      <strong>
       <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree2.png" style="width: 150px; height: 142px;">
      </strong>
     </p>
     <pre>
<strong>Input: </strong><span id="example-input-2-1">[0,3,0]</span>
<strong>Output: </strong><span id="example-output-2">3</span>
<strong>Explanation: </strong>From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.
</pre>
     <div>
      <p>
       <strong>
        Example 3:
       </strong>
      </p>
      <p>
       <strong>
        <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree3.png" style="width: 150px; height: 142px;">
       </strong>
      </p>
      <pre>
<strong>Input: </strong><span id="example-input-3-1">[1,0,2]</span>
<strong>Output: </strong><span id="example-output-3">2</span>
</pre>
      <div>
       <p>
        <strong>
         Example 4:
        </strong>
       </p>
       <p>
        <strong>
         <img alt="" src="https://assets.leetcode.com/uploads/2019/01/18/tree4.png" style="width: 155px; height: 156px;">
        </strong>
       </p>
       <pre>
<strong>Input: </strong><span id="example-input-4-1">[1,0,0,null,3]</span>
<strong>Output: </strong><span id="example-output-4">4</span>
</pre>
       <p>
        &nbsp;
       </p>
       <p>
        <strong>
         <span>
          Note:
         </span>
        </strong>
       </p>
       <ol>
        <li>
         <code>
          1&lt;= N &lt;= 100
         </code>
        </li>
        <li>
         <code>
          0 &lt;= node.val &lt;= N
         </code>
        </li>
       </ol>
      </div>
     </div>
    </div>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    1021. 在二叉树中分配硬币
   </h1>
   <p>
    给定一个有
    <code>
     N
    </code>
    个结点的二叉树的根结点
    <code>
     root
    </code>
    ，树中的每个结点上都对应有
    <code>
     node.val
    </code>
    枚硬币，并且总共有
    <code>
     N
    </code>
    枚硬币。
   </p>
   <p>
    在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
   </p>
   <p>
    返回使每个结点上只有一枚硬币所需的移动次数。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/01/19/tree1.png" style="height: 142px; width: 150px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>[3,0,0]
<strong>输出：</strong>2
<strong>解释：</strong>从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/01/19/tree2.png" style="height: 142px; width: 150px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>[0,3,0]
<strong>输出：</strong>3
<strong>解释：</strong>从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。
</pre>
   <p>
    <strong>
     示例 3：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/01/19/tree3.png" style="height: 142px; width: 150px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>[1,0,2]
<strong>输出：</strong>2
</pre>
   <p>
    <strong>
     示例 4：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/01/19/tree4.png" style="height: 156px; width: 155px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>[1,0,0,null,3]
<strong>输出：</strong>4
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1&lt;= N &lt;= 100
     </code>
    </li>
    <li>
     <code>
      0 &lt;= node.val &lt;= N
     </code>
    </li>
   </ol>
  </div>
 </body>
</html>